package Work;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 *  给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。
 *     请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。
 */

//////////////////////////// Java 答案﻿ /////////////////////////////
/*
    解题思路:
      1. 从后往前遍历数组，将nums1和nums2中的元素逐个比较
         将较大的元素往nums1末尾进行搬移
      2. 第一步结束后，nums2中可能会有数据没有搬移完，将nums2中剩余的元素逐个搬移到nums1

   ﻿时间复杂度：O(m+n)
   空间复杂度: O(1)
*/
class Solution1 {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        // end1、end2：分别标记nums1 和 nums2最后一个有效元素位置
        // end标记nums1的末尾，因为nums1和nums2中的元素从后往前往nums1中存放
        // ，否则会存在数据覆盖
        int end1 = m-1;
        int end2 = n-1;
        int end = nums1.length-1;

        // 从后往前遍历，将num1或者nums2中较大的元素往num1中end位置搬移
        // 直到将num1或者num2中有效元素全部搬移完
        while(end1 >= 0 && end2 >= 0){
            if(nums1[end1] > nums2[end2]){
                nums1[end--] = nums1[end1--];
            }else{
                nums1[end--] = nums2[end2--];
            }
        }

        // 如果nums2中的数据没有搬移完，搬移剩余nums中的元素
        while(end2 >= 0){
            nums1[end--] = nums2[end2--];
        }

        // num1中可能有数据没有搬移完，不用管，因为这些元素已经在nums1中了
    }
}
public class Test2 {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int k=0;
        for (int i = m; i < m+n ; i++) {
            nums1[i]=nums2[k];
            k++;
        }
        Arrays.sort(nums1);
    }
    public void Print(int[] nums1){
        for (int i = 0; i < nums1.length; i++) {
            System.out.print(nums1[i]+" ");
        }
    }

    public static void main(String[] args) {
        Test2 T2=new Test2();
        int[] nums1=new int[]{1,2,3,0,0,0};
        int[] nums2=new int[]{2,5,6};
        T2.merge(nums1,3,nums2,3);
        T2.Print(nums1);


    }


}
